{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Can Convert String in K Moves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canConvertString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 次操作转变字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>s</code>&nbsp;和&nbsp;<code>t</code>&nbsp;，你的目标是在 <code>k</code>&nbsp;次操作以内把字符串&nbsp;<code>s</code>&nbsp;转变成&nbsp;<code>t</code>&nbsp;。</p>\n",
    "\n",
    "<p>在第 <code>i</code>&nbsp;次操作时（<code>1 &lt;= i &lt;= k</code>），你可以选择进行如下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择字符串 <code>s</code>&nbsp;中满足 <code>1 &lt;= j &lt;= s.length</code>&nbsp;且之前未被选过的任意下标 <code>j</code>&nbsp;（下标从 1 开始），并将此位置的字符切换 <code>i</code>&nbsp;次。</li>\n",
    "\t<li>不进行任何操作。</li>\n",
    "</ul>\n",
    "\n",
    "<p>切换 1 个字符的意思是用字母表中该字母的下一个字母替换它（字母表环状接起来，所以 <code>'z'</code>&nbsp;切换后会变成 <code>'a'</code>）。第 <code>i</code>&nbsp;次操作意味着该字符应切换&nbsp;<code>i</code>&nbsp;次</p>\n",
    "\n",
    "<p>请记住任意一个下标 <code>j</code>&nbsp;最多只能被操作&nbsp;1 次。</p>\n",
    "\n",
    "<p>如果在不超过 <code>k</code>&nbsp;次操作内可以把字符串 <code>s</code>&nbsp;转变成 <code>t</code>&nbsp;，那么请你返回&nbsp;<code>true</code>&nbsp;，否则请你返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"input\", t = \"ouput\", k = 9\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>第 6 次操作时，我们将 'i' 切换 6 次得到 'o' 。第 7 次操作时，我们将 'n' 切换 7 次得到 'u' 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abc\", t = \"bcd\", k = 10\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 'a' 切换成 'b' ，但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aab\", t = \"bbb\", k = 27\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>第 1 次操作时，我们将第一个 'a' 切换 1 次得到 'b' 。在第 27 次操作时，我们将第二个字母 'a' 切换 27 次得到 'b' 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, t.length &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10^9</code></li>\n",
    "\t<li><code>s</code>&nbsp;和&nbsp;<code>t</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [can-convert-string-in-k-moves](https://leetcode.cn/problems/can-convert-string-in-k-moves/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [can-convert-string-in-k-moves](https://leetcode.cn/problems/can-convert-string-in-k-moves/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"input\"\\n\"ouput\"\\n9', '\"abc\"\\n\"bcd\"\\n10', '\"aab\"\\n\"bbb\"\\n27']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "\n",
    "        n = len(s)\n",
    "        if len(t) != n:\n",
    "            return False\n",
    "        cnt = [0]*26\n",
    "        \n",
    "        for i in range(n):\n",
    "            a = ord(s[i])-ord(\"a\")\n",
    "            b = ord(t[i])-ord(\"a\")\n",
    "            if a != b:\n",
    "                x = (b-a)%26\n",
    "                y = cnt[x]*26+x\n",
    "                cnt[x] += 1\n",
    "                if y > k:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        dic = {}\n",
    "        for i in range(len(s)):\n",
    "            x = ord(t[i]) - ord(s[i])\n",
    "            if x < 0:\n",
    "                x += 26\n",
    "            if x > k:\n",
    "                return False\n",
    "            if x != 0:\n",
    "                if x not in dic:\n",
    "                    dic[x] = 0\n",
    "                else:\n",
    "                    dic[x] += 1\n",
    "                    if x + dic[x] * 26 > k:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        change = [0 for i in range(26)]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != t[i]:\n",
    "                tmp = ord(t[i])-ord(s[i])\n",
    "                if tmp < 0:\n",
    "                    tmp += 26\n",
    "                if change[tmp]*26+tmp > k:\n",
    "                    return False\n",
    "                else:\n",
    "                    change[tmp] += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        dic = {}\n",
    "        for i in range(len(s)):\n",
    "            x = ord(t[i]) - ord(s[i])\n",
    "            if x < 0:\n",
    "                x += 26\n",
    "            if x != 0:\n",
    "                if x not in dic:\n",
    "                    dic[x] = 0\n",
    "                else:\n",
    "                    dic[x] += 1\n",
    "        for x, y in dic.items():\n",
    "            if x + y * 26 > k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        \n",
    "        counts = [0] * 26\n",
    "        for si, ti in zip(s, t):\n",
    "            difference = ord(ti) - ord(si)\n",
    "            if difference < 0:\n",
    "                difference += 26\n",
    "            counts[difference] += 1\n",
    "        \n",
    "        for i, count in enumerate(counts[1:], 1):\n",
    "            maxConvert = i + 26 * (counts[i] - 1)\n",
    "            if maxConvert > k:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s)!=len(t): return False\n",
    "        book=Counter(val if val>0 else 26+val for x,y in zip(s,t) if (val:=ord(y)-ord(x)))\n",
    "        return all(26*(cnt-1)+diff<=k for diff,cnt in book.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        dic = {}\n",
    "        for i in range(len(s)):\n",
    "            x = ord(t[i]) - ord(s[i])\n",
    "            if x < 0:\n",
    "                x += 26\n",
    "            if x != 0:\n",
    "                if x not in dic:\n",
    "                    dic[x] = 0\n",
    "                else:\n",
    "                    dic[x] += 1\n",
    "                    if x + dic[x] * 26 > k:\n",
    "                        return False\n",
    "        if dic:\n",
    "            return max(dic) <= k\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        \n",
    "        counts = [0] * 26\n",
    "        for si, ti in zip(s, t):\n",
    "            difference = ord(ti) - ord(si)\n",
    "            if difference < 0:\n",
    "                difference += 26\n",
    "            counts[difference] += 1\n",
    "        \n",
    "        for i, count in enumerate(counts[1:], 1):\n",
    "            maxConvert = i + 26 * (count - 1)\n",
    "            if maxConvert > k:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        cnt = [k // 26] * 26  # 可以切换i次的个数\n",
    "        k %= 26\n",
    "        for i in range(1, k + 1):\n",
    "            cnt[i] += 1\n",
    "        if len(s) != len(t): return False\n",
    "        for i in range(len(s)):\n",
    "            j = (ord(t[i]) - ord(s[i]) + 26) % 26\n",
    "            if j != 0:\n",
    "                if cnt[j] > 0:\n",
    "                    cnt[j] -= 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        cnt = defaultdict(int)\n",
    "        for x,y in zip(s,t):\n",
    "            if x != y:\n",
    "                dis = (ord(y) - ord(x)) % 26\n",
    "                cnt[dis] += 1\n",
    "                if dis+26*(cnt[dis] - 1) > k:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        counts = [0] * 26\n",
    "        for a, b in zip(s, t):\n",
    "            cnt = ord(b) - ord(a)\n",
    "            if cnt < 0: cnt += 26\n",
    "            counts[cnt] += 1\n",
    "        \n",
    "        for i, x in enumerate(counts[1:], 1):\n",
    "            maxcnt = i + 26 * (x - 1)\n",
    "            if maxcnt > k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        dic = {}\n",
    "        for i in range(len(s)):\n",
    "            x = ord(t[i]) - ord(s[i])\n",
    "            if x < 0:\n",
    "                x += 26\n",
    "            if x != 0:\n",
    "                if x not in dic:\n",
    "                    dic[x] = 0\n",
    "                else:\n",
    "                    dic[x] += 1\n",
    "                    if x + dic[x] * 26 > k:\n",
    "                        return False\n",
    "        if dic:\n",
    "            return max(dic) <= k\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "        if m != n:\n",
    "            return False\n",
    "        cur = [0] * 26\n",
    "        for si, ti in zip(s, t):\n",
    "            difference = ord(ti) - ord(si)\n",
    "            if difference < 0:\n",
    "                difference += 26\n",
    "            cur[difference] += 1\n",
    "        for i, value in enumerate(cur[1:], 1):\n",
    "            maxCount = i + 26 *(value - 1)\n",
    "            if maxCount > k:\n",
    "                return False\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        dic = {}\n",
    "        for i in range(len(s)):\n",
    "            x = ord(t[i]) - ord(s[i])\n",
    "            if x < 0:\n",
    "                x += 26\n",
    "            if x != 0:\n",
    "                if x not in dic:\n",
    "                    dic[x] = 0\n",
    "                else:\n",
    "                    dic[x] += 1\n",
    "        for x, y in dic.items():\n",
    "            if x + y * 26 > k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        \n",
    "        counts = [0] * 26\n",
    "        for si, ti in zip(s, t):\n",
    "            difference = ord(ti) - ord(si)\n",
    "            if difference < 0:\n",
    "                difference += 26\n",
    "            counts[difference] += 1\n",
    "        \n",
    "        for i, count in enumerate(counts[1:], 1):\n",
    "            maxConvert = i + 26 * (counts[i] - 1)\n",
    "            if maxConvert > k:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        lens = len(s)\n",
    "        lent = len(t)\n",
    "        if lens != lent:\n",
    "            return False\n",
    "        # d = []\n",
    "        # for i in range(lens):\n",
    "        #     if s[i] != t[i]:\n",
    "        #         d.append((s[i], t[i]))\n",
    "        # rever = [i + 1 for i in range(k)]\n",
    "        # for i in d:\n",
    "        #     need2change = ord(i[0])\n",
    "        #     tar = ord(i[1])\n",
    "        #     if tar - need2change > 0:\n",
    "        #         num = tar - need2change\n",
    "        #     else:\n",
    "        #         num = 26 + tar - need2change\n",
    "        #     if num in rever:\n",
    "        #         rever.remove(num)\n",
    "        #     else:\n",
    "        #         f = False\n",
    "        #         while num <= k:\n",
    "        #             if num in rever:\n",
    "        #                 rever.remove(num)\n",
    "        #                 f = True\n",
    "        #                 break\n",
    "        #             num += 26\n",
    "        #         if not f:\n",
    "        #             return False\n",
    "        # return True\n",
    "\n",
    "        counts = [0] * 26\n",
    "        for si, ti in zip(s, t):\n",
    "            difference = ord(ti) - ord(si)\n",
    "            if difference < 0:\n",
    "                difference += 26\n",
    "            counts[difference] += 1\n",
    "        \n",
    "        for i, count in enumerate(counts[1:], 1):\n",
    "            maxConvert = i + 26 * (counts[i] - 1)\n",
    "            if maxConvert > k:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        \n",
    "        cnt = [0] * 26\n",
    "        for si, ti in zip(s, t):\n",
    "            diff = ord(ti) - ord(si)\n",
    "            if diff < 0:\n",
    "                diff += 26\n",
    "            cnt[diff] += 1\n",
    "\n",
    "        for i, count in enumerate(cnt[1:], 1):\n",
    "            maxConvert = i + 26 * (cnt[i] - 1)\n",
    "            if maxConvert > k:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        f=Counter()\n",
    "        for x,y in zip(s,t):\n",
    "           if x ==y:\n",
    "               continue \n",
    "           \n",
    "           r=ord(y)-ord(x)\n",
    "           if r<0:\n",
    "               r+=26\n",
    "           f[r]+=1\n",
    "        mx=0\n",
    "        cur=0       \n",
    "        for x in f.items():\n",
    "           cur+=x[1] \n",
    "           if mx<x[0]+26*(x[1]-1):\n",
    "              mx=x[0]+26*(x[1]-1)\n",
    "        return mx<=k and len(s)==len(t) and cur<=k        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "\n",
    "\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "\n",
    "        counts = [0] * 26\n",
    "\n",
    "        for si, ti in zip(s,t):\n",
    "            diff = (ord(ti) - ord(si) + 26) % 26\n",
    "            counts[diff] += 1\n",
    "        \n",
    "        for i, count in enumerate(counts[1:], 1):\n",
    "\n",
    "            maxConvert = i + 26 * (counts[i] - 1)\n",
    "            if maxConvert > k:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        record = [0]*26\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        for i in range(len(s)):\n",
    "            if s[i]!=t[i]:\n",
    "                diff = ord(t[i])-ord(s[i])\n",
    "                if diff<0:\n",
    "                    diff += 26\n",
    "\n",
    "                record[diff] += 1\n",
    "\n",
    "        for idx,count in enumerate(record):\n",
    "            maxConvert = idx+26*(count-1)\n",
    "            if maxConvert>k:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        n, m = len(s), len(t)\n",
    "        if n != m: return False\n",
    "\n",
    "        mx = 0\n",
    "        mp = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            if s[i] != t[i]:\n",
    "                d = (ord(t[i]) - ord(s[i])) % 26\n",
    "                mp[d] += 1\n",
    "                mx = max(mx, d + 26 * (mp[d] - 1))\n",
    "        return mx <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t): return False\n",
    "        i = 0\n",
    "        d = [0] * 26\n",
    "        while i < len(s):\n",
    "            if s[i] != t[i]:\n",
    "                temp = (ord(t[i]) - ord(s[i]) + 26) % 26\n",
    "                d[temp] += 1\n",
    "            i += 1\n",
    "        for i in range(26):\n",
    "            if d[i] * 26 + i - 26 > k: return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        ans = [0] * 26\n",
    "        for i in range(len(s)):\n",
    "            x = ord(t[i]) - ord(s[i])\n",
    "            if x < 0:\n",
    "                x += 26\n",
    "            if ans[x] > 0:\n",
    "                ans[x] += 26\n",
    "            else:\n",
    "                ans[x] = x\n",
    "            if ans[x] > k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "\n",
    "\n",
    "\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "\n",
    "        counts = [0] * 26\n",
    "\n",
    "        for si, ti in zip(s,t):\n",
    "            diff = (ord(ti) - ord(si) + 26) % 26\n",
    "            counts[diff] += 1\n",
    "        \n",
    "\n",
    "        for i, count in enumerate(counts[1:], 1):\n",
    "\n",
    "            maxConvert = i + 26 * (counts[i] - 1)\n",
    "            if maxConvert > k:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        n, m = len(s), len(t)\n",
    "        if n != m: return False\n",
    "\n",
    "        mp = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            if s[i] != t[i]: mp[(ord(t[i]) - ord(s[i])) % 26] += 1\n",
    "        mx = 0\n",
    "        for key, v in mp.items():\n",
    "            mx = max(mx, key + 26 * (v - 1))\n",
    "        return mx <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "\n",
    "\n",
    "\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "\n",
    "        counts = [0] * 26\n",
    "\n",
    "        for si, ti in zip(s,t):\n",
    "            diff = ord(ti) - ord(si)\n",
    "            if diff < 0:\n",
    "                diff += 26\n",
    "\n",
    "            counts[diff] += 1\n",
    "        \n",
    "\n",
    "        for i, count in enumerate(counts[1:], 1):\n",
    "\n",
    "            maxConvert = i + 26 * (counts[i] - 1)\n",
    "            if maxConvert > k:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        cnts = [0] * 26\n",
    "        for c1,c2 in zip(s,t):\n",
    "            idx = (ord(c2)-ord(c1)) % 26\n",
    "            cnts[idx] += 1\n",
    "            if idx and idx + (cnts[idx]-1) * 26 > k:\n",
    "                return False \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\r\n",
    "        if len(s) != len(t):\r\n",
    "            return False\r\n",
    "        h = [0] * 26\r\n",
    "        for i in range(len(s)):\r\n",
    "            if t[i] == s[i]:\r\n",
    "                continue\r\n",
    "            if ord(t[i]) > ord(s[i]):\r\n",
    "                h[ord(t[i]) - ord(s[i])] += 1\r\n",
    "            else:\r\n",
    "                h[26 - ord(s[i]) + ord(t[i])] += 1\r\n",
    "        for i in range(1, 26):\r\n",
    "            if (k - i + 26) // 26 < h[i]:\r\n",
    "                return False\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "\n",
    "        n = len(s)\n",
    "        dist_cnt = [0 for _ in range(26)]\n",
    "        for i in range(n):\n",
    "            d = ord(t[i]) - ord(s[i])\n",
    "            if d < 0:\n",
    "                d += 26\n",
    "            dist_cnt[d] += 1\n",
    "\n",
    "        for d in range(1, 26):\n",
    "            cur_maxsize = d + 26 * (dist_cnt[d] - 1)\n",
    "            if cur_maxsize > k:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        cnts = [0] * 26\n",
    "        for c1,c2 in zip(s,t):\n",
    "            idx = (ord(c2)-ord(c1)) % 26\n",
    "            cnts[idx] += 1\n",
    "\n",
    "        for idx, cnt in enumerate(cnts[1:], 1):\n",
    "            if idx + (cnt-1) * 26 > k:\n",
    "                return False \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        cnt = [0] * 26\n",
    "        for c1, c2 in zip(s, t):\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            diff = ord(c2) - ord(c1)\n",
    "            if diff < 0:\n",
    "                diff = 26 + diff\n",
    "            cnt[diff] += 1\n",
    "        m = max(cnt)\n",
    "        for i in range(25, -1, -1):\n",
    "            if cnt[i] == m:\n",
    "                return (m - 1) * 26 + i <= k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t): return False\n",
    "\n",
    "        visit = defaultdict(int)\n",
    "        each, mod = k // 26, k % 26\n",
    "        for i in range(1, 27):\n",
    "            visit[i] += each\n",
    "        for j in range(1, mod + 1):\n",
    "            visit[j] += 1\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            sw, tw = ord(s[i]), ord(t[i])\n",
    "            if sw != tw:\n",
    "                if sw > tw: tw += 26\n",
    "                ans = tw - sw\n",
    "                if visit[ans] > 0:\n",
    "                    visit[ans] -= 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        tmp = list((ord(c2) - ord(c1) + 26) % 26 for c1, c2 in zip(s, t))\n",
    "        return all(x <= k for x in tmp)\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        visit = set()\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != t[i]:\n",
    "                tmp = (ord(t[i]) - ord(s[i]) + 26) % 26\n",
    "                while tmp in visit:\n",
    "                    tmp += 26\n",
    "                if tmp > k:\n",
    "                    return False\n",
    "                visit.add(tmp)\n",
    "        return (len(s) == len(t))\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t): return False\n",
    "        tmp = list((ord(c2) - ord(c1) + 26) % 26 for c1, c2 in zip(s, t))\n",
    "        for key, v in Counter(tmp).items():\n",
    "            if key and key + (v - 1) * 26 > k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        c = Counter([ord(tt) - ord(ss) if ord(tt) - ord(ss) >= 0 else ord(tt) - ord(ss) + 26 for ss,tt in zip(s,t)])\n",
    "        need = 0\n",
    "        for ck in c.keys():\n",
    "            if ck > 0 and c[ck] > 0:\n",
    "                need = max(need, ck + 26*(c[ck] - 1))\n",
    "        return need <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if (len(s) != len(t)): return False\n",
    "        dist = [0] * len(s)\n",
    "        for i, (x, y) in enumerate(zip(s, t)):\n",
    "            dist[i] = (ord(y) - ord(x) + 26) % 26\n",
    "        \n",
    "        dist.sort()\n",
    "        pre = -1\n",
    "        for x in dist:\n",
    "            if x > 0 and x % 26 == pre % 26:\n",
    "                x = pre + 26\n",
    "            if x > k:\n",
    "                return False\n",
    "            pre = x\n",
    "        return True\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConvertString(self, s: str, t: str, k: int) -> bool:\n",
    "        if len(s) != len(t):\n",
    "            return False\n",
    "        n = len(s)\n",
    "        dis = {}\n",
    "        maxval = 0\n",
    "        val = 0\n",
    "        l = []\n",
    "        for i in range(n):\n",
    "            if ord(s[i]) <= ord(t[i]):\n",
    "                val = ord(t[i]) - ord(s[i])\n",
    "            else:\n",
    "                val = 26 - ord(s[i]) + ord(t[i])\n",
    "            l.append(val)\n",
    "            if val == 0:\n",
    "                continue\n",
    "            if val in dis:\n",
    "                maxval = max(maxval,dis[val]*26 + val)\n",
    "                dis[val] = dis[val] + 1\n",
    "            else:\n",
    "                maxval = max(maxval,val)\n",
    "                dis[val] = 1\n",
    "        if maxval > k:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
